<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta name="generator" content="AsciiDoc 7.1.2" />
<style type="text/css">
/* Debug borders */
p, li, dt, dd, div, pre, h1, h2, h3, h4, h5, h6 {
/*
  border: 1px solid red;
*/
}

body {
  margin: 1em 5% 1em 5%;
}

a {
  color: blue;
  text-decoration: underline;
}
a:visited {
  color: fuchsia;
}

em {
  font-style: italic;
}

strong {
  font-weight: bold;
}

tt {
  color: navy;
}

h1, h2, h3, h4, h5, h6 {
  color: #527bbd;
  font-family: sans-serif;
  margin-top: 1.2em;
  margin-bottom: 0.5em;
  line-height: 1.3;
}

h1 {
  border-bottom: 2px solid silver;
}
h2 {
  border-bottom: 2px solid silver;
  padding-top: 0.5em;
}

div.sectionbody {
  font-family: serif;
  margin-left: 0;
}

hr {
  border: 1px solid silver;
}

p {
  margin-top: 0.5em;
  margin-bottom: 0.5em;
}

pre {
  padding: 0;
  margin: 0;
}

span#author {
  color: #527bbd;
  font-family: sans-serif;
  font-weight: bold;
  font-size: 1.2em;
}
span#email {
}
span#revision {
  font-family: sans-serif;
}

div#footer {
  font-family: sans-serif;
  font-size: small;
  border-top: 2px solid silver;
  padding-top: 0.5em;
  margin-top: 4.0em;
}
div#footer-text {
  float: left;
  padding-bottom: 0.5em;
}
div#footer-badges {
  float: right;
  padding-bottom: 0.5em;
}

div#preamble,
div.tableblock, div.imageblock, div.exampleblock, div.verseblock,
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
div.admonitionblock {
  margin-right: 10%;
  margin-top: 1.5em;
  margin-bottom: 1.5em;
}
div.admonitionblock {
  margin-top: 2.5em;
  margin-bottom: 2.5em;
}

div.content { /* Block element content. */
  padding: 0;
}

/* Block element titles. */
div.title, caption.title {
  font-family: sans-serif;
  font-weight: bold;
  text-align: left;
  margin-top: 1.0em;
  margin-bottom: 0.5em;
}
div.title + * {
  margin-top: 0;
}

td div.title:first-child {
  margin-top: 0.0em;
}
div.content div.title:first-child {
  margin-top: 0.0em;
}
div.content + div.title {
  margin-top: 0.0em;
}

div.sidebarblock > div.content {
  background: #ffffee;
  border: 1px solid silver;
  padding: 0.5em;
}

div.listingblock > div.content {
  border: 1px solid silver;
  background: #f4f4f4;
  padding: 0.5em;
}

div.quoteblock > div.content {
  padding-left: 2.0em;
}

div.attribution {
  text-align: right;
}
div.verseblock + div.attribution {
  text-align: left;
}

div.admonitionblock .icon {
  vertical-align: top;
  font-size: 1.1em;
  font-weight: bold;
  text-decoration: underline;
  color: #527bbd;
  padding-right: 0.5em;
}
div.admonitionblock td.content {
  padding-left: 0.5em;
  border-left: 2px solid silver;
}

div.exampleblock > div.content {
  border-left: 2px solid silver;
  padding: 0.5em;
}

div.verseblock div.content {
  white-space: pre;
}

div.imageblock div.content { padding-left: 0; }
div.imageblock img { border: 1px solid silver; }
span.image img { border-style: none; }

dl {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
dt {
  margin-top: 0.5em;
  margin-bottom: 0;
  font-style: italic;
}
dd > *:first-child {
  margin-top: 0;
}

ul, ol {
    list-style-position: outside;
}
ol.olist2 {
  list-style-type: lower-alpha;
}

div.tableblock > table {
  border: 3px solid #527bbd;
}
thead {
  font-family: sans-serif;
  font-weight: bold;
}
tfoot {
  font-weight: bold;
}

div.hlist {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
td.hlist1 {
  vertical-align: top;
  font-style: italic;
  padding-right: 0.8em;
}
td.hlist2 {
  vertical-align: top;
}

@media print {
  div#footer-badges { display: none; }
}
include1::./stylesheets/xhtml11-manpage.css[]
/* Workarounds for IE6's broken and incomplete CSS2. */

div.sidebar-content {
  background: #ffffee;
  border: 1px solid silver;
  padding: 0.5em;
}
div.sidebar-title, div.image-title {
  font-family: sans-serif;
  font-weight: bold;
  margin-top: 0.0em;
  margin-bottom: 0.5em;
}

div.listingblock div.content {
  border: 1px solid silver;
  background: #f4f4f4;
  padding: 0.5em;
}

div.quoteblock-content {
  padding-left: 2.0em;
}

div.exampleblock-content {
  border-left: 2px solid silver;
  padding-left: 0.5em;
}
</style>
<title>CANONS (1)</title>
</head>
<body>
<div id="header">
<h1>
CANONS (1) Manual Page
</h1>
<h2>NAME</h2>
<div class="sectionbody">
<p>Canons -
   Brings Sudokus in a canonical form.
</p>
</div>
</div>
<h2>SYNOPSIS</h2>
<div class="sectionbody">
<p><em>canons</em> &lt;infile &gt;outfile</p>
</div>
<h2>DESCRIPTION</h2>
<div class="sectionbody">
<p><em>canons</em> reads Sudokus from standard input, one per line (and with a zero <em>0</em>
representing an empty cell). It prints them to standard output in the same
sequence, transformed to their canonical form. The canonical form the one
that is the lowest in lexicographic order of all the representations that can
be generated by a set of transformations that don't change the game's logic.</p>
<p>These transformations are:</p>
<ul>
<li>
<p>
reordering of columns and rows within the same 3x3 blcok
</p>
</li>
<li>
<p>
reordering of columns and rows block wise
</p>
</li>
<li>
<p>
transposition
</p>
</li>
<li>
<p>
permutation (that means renumbering)
</p>
</li>
</ul>
</div>
<h2>OPTIONS</h2>
<div class="sectionbody">
<p>None</p>
</div>
<h2>BUGS</h2>
<div class="sectionbody">
<p>canons only performs very basic input sanitations, you should not use it in a
hostile environment (e.g. web server).</p>
<p>canons is slow, but that seems to be due to the problem, not due to poor
programming.</p>
</div>
<h2>IMPLEMENTATION DETAILS</h2>
<div class="sectionbody">
<p>This section is not important, you may just as well skip it. It contains some
developement informations.</p>
<p><em>canons</em> is written in C++. It uses no C++ features except input/output, so
transition to C should be easy (I'm working on it ;-).</p>
<p>The largest part of the source code is a static array of 6^4 permutations of
the number 0 &#8230; 8, representing the transformations described in section
<tt>DESCRIPTION</tt>.</p>
<p>For each Suodku read from standard input a Sudoku is stored which is the
lexicographic least of all computed transformations so far. All of the
6<sup>4 <strong> 6</sup>4 </strong> 2 transformations are computed, but only as far as needed to
decide whether that transformation is lexicographic smaller than the current
minimum. If it is smaller, the minimum is update to the current
transformation.</p>
<p>So far I haven't found a way to compute a canonical form without applying all
possible transformations.</p>
</div>
<h2>AUTHOR</h2>
<div class="sectionbody">
<p>Written by Moritz Andreas Lenz, &lt;<a href="mailto:moritz@faui2k3.org">moritz@faui2k3.org</a>&gt;</p>
</div>
<h2>RESOURCES</h2>
<div class="sectionbody">
<p>Project page: <a href="http://moritz.faui2k3.org/proejcts#canons">http://moritz.faui2k3.org/proejcts#canons</a></p>
<p>Google Code project page: <a href="http://code.google.com/p/canons">http://code.google.com/p/canons</a></p>
<p>More on Sudoku: <a href="http://moritz.faui2k3.org/sudoku">http://moritz.faui2k3.org/sudoku</a></p>
</div>
<h2>COPYING</h2>
<div class="sectionbody">
<p>Copyright (C) 2006 <a href="http://moritz.faui2k3.org/">Moritz Andreas Lenz</a>. Free use of this software is granted
under the terms of the GNU General Public License (GPL) or under the Artistic
License. See the file LICENSE for details.</p>
</div>
<div id="footer">
<div id="footer-text">
Last updated 04-Aug-2006 14:36:55 CEST
</div>
</div>
</body>
</html>
